1. Field of the Invention
This invention relates to transform coding for digital signals, and more particularly to coding for video signals.
2. Description of the Related Art
A linear transform coding system is known as a coding system for an audio or video signal. In the linear transform coding system, a plurality of discrete signals are linearly transformed first to obtain transform coefficients and then the transform coefficients are coded. By suitable selection of the base of the linear transform taking statistical characteristics of the signals into consideration, compression coding can be realized. It is known that a coding system which employs discrete cosine transform as such linear transform can achieve the highest compression coding of signals which conform to a highly correlated Markov probability model, and is utilized widely for international standardized systems.
While the discrete cosine transform is useful to achieve high compression coding in this manner, since it uses real numbers for the base of the transform, in order to realize lossless reversible coding, the quantization step size must be set small. This, however, gives rise to a disadvantage that the coding efficiency is deteriorated.
A system which achieve reversible coding such as discrete cosine transform without such deterioration in coding efficiency have been proposed. It is a "Lossless Transform Coding System for Digital Signals" proposed precedently by Mutsumi Ohta, one of the inventors of the present invention. In this system, reversible quantization is performed taking a discrete structure of transform coefficients using an integer matrix to which the transform is approximated to achieve reversible coding. In the following, the principle of this system is described.
According to the system, a transform matrix is multiplied by fixed numbers for individual rows and half-adjusted to obtain another matrix whose elements are integers, and then, integer N-element original signal vectors (x.sub.0, . . . , x.sub.N-1) are transformed with the integer matrix to obtain vectors (hereinafter referred to as transform points) (X.sub.0, . . . , X.sub.N-1) in a transform domain. While reversible coding can be achieved by the transform, since the density of the transform points is given by a reciprocal number 1/D to the determinant D of the integer matrix used for the transform, as the value of D increases, the number of useless integer points which do not make transform points in the transform domain increases, resulting in deterioration of the coding efficiency.
In order to eliminate such redundancies, reversible quantization is performed taking a discrete structure of transform points into consideration. It can be proved that the transform point structure has a period D with regard to each axis. Therefore, if the quantization periods of the individual axes which are multiples of D are represented by (d.sub.0, . . . , d.sub.N-1) and reversible quantization in regions of 0.ltoreq.X.sub.0.ltoreq.d.sub.0 -1, . . . 0.ltoreq.X.sub.N-1.ltoreq.d.sub.N-1 -1 around the origin is defined artificially, then reversible quantization of an arbitrary transform point can be performed making use of the periodicity.
First, (X.sub.0, . . . X.sub.N-1) are divided by the quantization periods (d.sub.0, . . . , d.sub.N-1) to obtain quotients (a.sub.0, . . . , a.sub.N-1) and remainders (r.sub.0, . . . r.sub.N-1), respectively, and the quantization defined as above is performed for the remainders (r.sub.0, . . . r.sub.N-1) to obtain quantization values (q.sub.0, . . . , q.sub.N-1) of the remainders (r.sub.0, . . . , r.sub.N-1), respectively. Then, calculation given by the following expression is performed to obtain quantization values (Q.sub.0. . . Q.sub.N-1) of the transform points: EQU Q.sub.i =a.sub.i m.sub.i +q.sub.i (i=0, . . . N-1) (1)
where m.sub.i (i=0, 1, . . . , N-1) is a width (range) of the possible values as q.sub.i. The redundancies of the transform points can be removed by quantization using the technique described above.
On the other hand, in inverse transform, (Q.sub.0, . . . , Q.sub.N-1) are first divided by (m.sub.0, . . . , m.sub.N-1) to obtain quotients (a.sub.0, . . . , a.sub.N-1) and remainders (q.sub.0, . . . , q.sub.N-1), respectively. Then, dequantization is performed for the remainders (q.sub.0, . . . , q.sub.N-1) to obtain (r.sub.0, . . . , r.sub.N-1). Then, calculation given by the following expression: EQU X.sub.i =a.sub.i d.sub.i +r.sub.i (i=0, . . . , N-1) (2)
is performed, thereby achieving reversible dequantization. After the dequantization, the transform points (X.sub.0, . . . , X.sub.N-1) are linearly transformed with an inverse matrix to the original integer matrix to obtain the original signals (x.sub.0, . . . , x.sub.N-1).
In two-element discrete cosine transform, a matrix is approximated with ##EQU1##
In this instance, since the determinant D is D=2, if reversible quantization is set in a basic region of 2.times.2, 4.times.4, 8.times.8, 16.times.8 or the like, reversible quantization for all inputs can be performed using the method described above.
In four-element discrete cosine transform, a matrix can be approximated, using suitable integers c.sub.2, c.sub.4 and c.sub.6, with a matrix transform of ##EQU2##
In this instance, an applicable high speed calculation method is available and can decompose the matrix transform into four 2.times.2 matrix transforms given by ##EQU3##
By applying the method described above to the individual transforms, reversible transform free from redundancies can be achieved readily.
In eight-element discrete cosine transform, a matrix can be approximated, using suitable integers c.sub.1, c.sub.2, c.sub.3, c.sub.4, c.sub.5, c.sub.6 and c.sub.7, with a matrix transform of ##EQU4##
Also in this instance, an applicable high speed calculation method is available and can decompose the matrix transform into matrix transforms given by ##EQU5##
Since the first eight transforms given by the expressions (10) to (17) are 2.times.2 matrix transforms, the method described above can be applied readily to them. However, the last 4.times.4 matrix transform given by the expression (18) requires such a large region for definition of quantization that a practical circuit for it cannot be realized. In particular, the determinant D of the matrix of the expression (18) is given by EQU D=(c.sub.1.sup.2 -c.sub.7.sup.2 +2c.sub.3 c.sub.5).sup.2 +(c.sub.3.sup.2 -c.sub.5.sup.2 +2c.sub.1 c.sub.7).sup.2 (19)
and the reciprocal number 1/D to D in this instance represents the density of the transform points. Consequently, in order to produce a quantization table using the technique described above, a table having at least D.sup.3 elements must be produced. Since the size of the table increases in proportion to the cube of the determinant D, where D is very large, it is difficult to realize the reversible quantization. For example, in the case of four-element discrete cosine transform by the aforementioned "Lossless Transform Coding System for Digital Signals" wherein (c.sub.1, c.sub.3, c.sub.5, c.sub.7)=(5, 4, 3, 1), since the determinant D is D=2,593, a quantization table having at least 2,593.sup.3 elements is required, which is not practical.
Further, in order to realize the eight-element reversible discrete cosine transform based on the method described above, such a circuit as shown in FIG. 6 is used. Where the circuit of FIG. 6 is employed, redundancies are removed by deleting the least significant bit of one of two calculation results for each butterfly calculation at the first and middle stages corresponding to the expressions (10) to (15) given hereinabove, the dynamic range of the calculation result from which the least significant bit has been deleted is reduced to 1/2 that of the other calculation result. As a result, the dynamic ranges of transform coefficients obtained finally are different among the different coefficients, and accordingly, the transform coefficients obtained finally are different in dynamic range from transform coefficients of actual discrete cosine transform.